// https://www.lintcode.com/problem/longest-word-in-dictionary-through-deleting/description
// 法一：双指针
class Solution {
public:
    bool check(string &s, string &t)
    {
        int i = 0, j = 0;
        while (i < s.length() && j < t.length() && (s.length() - i >= t.length() - j))
        {
            if (s[i] == t[j]) j++;
            i++;
        }
        if (j == t.length()) return true;
        return false;
    }
    string findLongestWord(string &s, vector<string> &d) {
        string result = "";
        for (int i = 0; i < d.size(); ++i)
        {
            string str = d[i];
            if (str.size() > result.size() || (str.size() == result.size() && str < result))
            {
                if (check(s, str)) result = str;
                cout << result << endl;
            }
        }
        return result;
    }
};

// 法二：每次查找元素，查找部分可以优化为logN（二分法）
// class Solution {
// public:
//     /**
//      * @param s: a string
//      * @param d: List[str]
//      * @return: return a string
//      */
//     bool check(string &s, string &t)
//     {
//         int pos = -1;
//         for (int j = 0; j < t.size(); ++j)
//         {
//             int tmp = s.find(t[j], pos + 1); //注意从pos+1开始找
//             if (tmp > pos) 
//             {
//                 pos = tmp;
//             }
//             else return false;
//         }
//         return true;
//     }
//     string findLongestWord(string &s, vector<string> &d) {
//         string result = "";
//         for (auto str: d)
//         {
//             cout << str << endl;
//             if (str.size() > result.size() || (str.size() == result.size() && str < result))
//             {
//                 if (check(s, str)) result = str;
//                 cout << result << endl;
//             }
//         }
//         return result;
//     }
// };